package main

import "fmt"

type Treenode struct {
	Value   int
	Left  *Treenode
	Right *Treenode
}

func FindCommonAncestor(root, p, q *Treenode) *Treenode{
	if root == nil{
		return nil
	}

	if root == q || root == p {
		return root
	}
	left := FindCommonAncestor(root.Left,p,q)
	right := FindCommonAncestor(root.Right,p,q)

	if left != nil && right != nil{
		return root

	}
	if left != nil{
		return left
	}

	return right

}

func main(){
	root := &Treenode{
		Value: 1,
		Left: &Treenode{
			Value: 2,
			Left: &Treenode{
				Value: 7,
			},
			Right: &Treenode{
				Value: 8,
			},
		},
		Right: &Treenode{
			Value: 5,
			Left: &Treenode{
				Value: 9,
			},
			Right: &Treenode{
				Value: 10,

			},
		},
	}
	p := root.Left.Right
	q := root.Right.Right
	common := FindCommonAncestor(root,p,q)
	fmt.Println("最近共同祖先节点是:", common.Value)

}